package cn.myworld.algorithm.symbol;

/**
 * 有序符号表
 * @param <Key>
 * @param <Value>
 */
public class OrderSymbolTable<Key extends Comparable<Key>, Value> {

    private Node head;
    private int N;

    private class Node {
        public Key key;
        public Value value;
        public Node next;
        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public OrderSymbolTable() {
        this.head = new Node(null, null, null);
        this.N = 0;
    }

    public int size() {
        return N;
    }
    public boolean isEmpty() {
        return N == 0;
    }

    // 插入键值对
    public void put(Key key, Value value) {
        // 定义两个Node变量，分别记录当前节点和上一个节点
        Node cur = head.next;
        Node pre = head;
        while (cur != null && key.compareTo(cur.key) > 0) {
            // 变换当前节点和前一节点
            pre = cur;
            cur = cur.next;
        }
        // 如果当前节点cur的key的键和要插入的key一样，则替换
        if (cur != null && key.compareTo(cur.key) == 0) {
            cur.value = value;
            return;
        }

        // 如果当前节点cur的key的键和要插入的key不一样，则把新节点插入到cur前
        Node newNode = new Node(key, value, cur);
        pre.next = newNode;

        // 元素个数+1
        N++;

    }
    // 删除key的键值对
    public void delete(Key key) {
        // 找到键为key的节点，把该节点从链表中删除
        Node n = head;
        while (n.next != null) {
            // 判断n节点的下一个节点的键是否为key，如果是，就删除节点
            if (n.next.key.equals(key)) {
                n.next = n.next.next;
                N--;
                return;
            }

            // 变换n
            n = n.next;
        }
    }
    // 获取key的value
    public Value get(Key key) {
        Node n = head;
        // 找到键为key的节点
        while (n.next != null) {
            // 变换n
            n = n.next;
            if (n.key.equals(key)) {
                return n.value;
            }
        }
        return null;
    }

}
